Verbum

АЛГАРЫ́ТМАЎ ТЭО́РЫЯ,

раздзел матэматыкі, які вывучае агульныя ўласцівасці алгарытмаў; тэарэт. аснова кібернетыкі, вылічальнай матэматыкі.

У інтуітыўным паняцці алгарытмы выкарыстоўваліся ў матэматыцы на працягу яе існавання. Дакладнае паняцце алгарытму сфарміравалася ў пач. 20 ст. і ўпершыню з’явілася ў працах матэматыкаў франц. Э.Барэля (1912) і ням. Г.Вейля (1921). Сістэматычная распрацоўка алгарытмаў тэорыі пачалася ў 1936, калі амер. матэматык А.Чэрч удакладніў паняцце алгарытмічна вылічальнай функцыі і прывёў прыклад невыліч. функцыі, англ. А.Цьюрынг і амер. Э.Пост удакладнілі паняцце алгарытму ў тэрмінах ідэалізаваных выліч. машын (машыны Цьюрынга—Поста); сав. матэматык А.М.Калмагораў прапанаваў выкарыстанне алгарытмаў тэорыі для абгрунтавання інфармацыі тэорыі (1965).

Адзін з гал. Кірункаў алгарытмаў тэорыі — вывучэнне невырашальнасці (вырашальнасці) алгарытмічных праблем, напр., у самой алгарытмаў тэорыі — праблема спынення універсальнай машыны Цьюрынга; у матэм. логіцы — праблема распазнавання тоесна праўдзівых формул злічэння прэдыкатаў 1-й ступені; у алгебры — праблема тоеснасці для паўгруп; у тапалогіі — праблема гомеамарфізму; у тэорыі лікаў — 10-я праблема Д.Гільберта. Даследаванні прывялі да ўзнікнення паняцця ступені невырашальнасці, вывучэння адпаведных матэм. структур і паказалі, што алгарытмічныя праблемы невырашальнасці маюць найб. ступень.

Літ.:

Мальцев А.И. Алгоритмы и рекурсивные функции. 2 изд. М., 1986;

Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. М., 1980.

Р.Т.Вальвачоў.

т. 1, с. 233